Матрицы переходов глобального и локального выравниваний

Построение глобального выравнивания с помощью алгоритма Нидельмана-Вунша.

Выравнивались две последовательности:

MKNW - последовательность из четырех первых аминокислотных остатков белка ALkh_Ecoli;
SMANE - та же последовательность, но с 1-м добавленным и 2-мя измененными остатками.

Оптимальный путь выравнивания

seq1:		_MKNW
seq2:		SMANE
      		_*.*.

В выравнивании имеется:

совпадающие а.о.	2
несовпадающие а.о.	2
гэп	1

Расчет веса выравнивания:

правила рассчета веса:

вес совпадения	2
вес замены	-1
штраф за гэп	-2

Вес выравнивания равен:
W=2*2-2*1-2=0.

Алгоритм Нидельмана-Вунша позволяет создавать выравнивания последовательностей с наибольшим весом.
при этом количество операций было бы равно 2^n+m
, если

n - длина первой последовательности
m - длина второй последовательности

Данный же алгоритм позволяет создать выравнивание с наибольшим весом за m*n операций благодаря использованию принципов динамического программирования:
в основе лежит таблица, каждая ячейка которой показывает наибольший вес выравнивания последовательностей , где первая из них записана в заголовке строк а вторая - в заголовке столбцов (первый элемент последовательности - первая аминокислота в заголове, а последняя - с номером ячейки). Первый столбец и первая строка заполняются штрафами за гэп, а каждая ячейка таблицы заполняется по следующему принципу:
для ячейки М_i,j выбирается максимальное значение из

(M_i-1,j - штраф за гэп) или (M_i,j-1 - штраф за гэп);
(M_i-1,j-1 - штраф за несоответствие а.о.) если i-й а.о. первой последовательности и j-й а.о. второй последовательности разные;
(M_i-1,j-1 + награда за соответствие а.о.) если i-й а.о. первой последовательности и j-й а.о. второй последовательности одинаковые;

Построение локального выравнивания с помощью алгоритма Смита-Ватермана.

Выравнивались те же последовательности, как и в первом случае.
Оптимальное локальное выравнивание выглядит следующим образом :

seq1:			  _MK    
seq2:			  SMA    
      		  	  _*.

Выравнивание

совпадающие а.о.	1
несовпадающие а.о.	1
гэп	1

Вес выравнивания равен:
W=2*1-1-2=-1.